package Offer.offer;

/**
 * 3,4,5,1,2
 * 旋转数组的最小数字
 * 1,1,0,1,1,1
 *
 * @author leiwenkang
 * @date 2020/4/6
 */
public class Test08旋转数组的最小数字 {
    public static void main(String[] args) {
//        int[]array={3,4,5,1,2};
        int[]array={1,2, 3,4,5};
//        System.out.println(findMin(array));
        System.out.println(minNumberInRotateArra2(array));
    }

    public static int findMin(int[] array) {
        if (array == null || array.length == 0) {
            throw new RuntimeException("数组为空");
        }


        //分各种情况，
        // 1,2,3,4,5未旋转
        if (array[0] < array[array.length - 1]) {
            return array[0];
        }

        //1,1,0,1,1,1的特殊情况，只能顺序遍历
        if (array[0] == array[array.length - 1] && array[0] == array[(array.length - 1) >> 1]) {
            return findMinByOrder(array);
        }

        int start = 0;
        int end = array.length - 1;
        //一般情况 3,4,5,1,2，二分查找
        while (end - start > 1) {
            int mid = (start + end) >> 1;
            if (array[mid] >= array[start]) {
                start = mid;
            } else if (array[mid] <= array[end]) {
                end = mid;
            }
        }
        return array[end];
    }

    private static int findMinByOrder(int[] array) {
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }

    public static int minNumberInRotateArra2(int [] array) {
        if(array.length==0) return 0;
        int left=0;
        int right=array.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(array[mid]>array[right]){//最小值在mid右边 mid大于最小值
                left=mid+1;
            }else if(array[mid]<array[right]){//最小值mid左边
                right=mid;
            }else{
                right--;
            }

        }
        return array[left];
    }
}
